#coding=utf-8

import sys

from aima.search import Node

def custom_depth_limited_search(problem, limit=50):
    "[Fig. 3.12]"
    def recursive_dls(node, problem, limit, visited_nodes):
        cutoff_occurred = False
        visited_by_others = visited_nodes
        if problem.goal_test(node.state):
            return (node, visited_nodes)
        elif node.depth == limit:
            return ('cutoff', visited_nodes)
        else:
            for successor in node.expand(problem):
                result, r_visited = recursive_dls(successor, problem, limit, visited_by_others)
                visited_by_others += r_visited
                if result == 'cutoff':
                    cutoff_occurred = True
                elif result != None:
                    return (result, visited_by_others + visited_nodes)
        if cutoff_occurred:
            return ('cutoff', visited_by_others + visited_nodes)
        else:
            return None
    # Body of depth_limited_search:
    return recursive_dls(Node(problem.initial), problem, limit, 1)

def custom_iterative_deepening_search(problem):
    "[Fig. 3.13]"
    for depth in xrange(sys.maxint):
        result, visited_nodes = custom_depth_limited_search(problem, depth)
        if result is not 'cutoff':
            return result, visited_nodes